The present invention generally relates to an image processing system for image compression and decompression, and more particularly to an image processing system for image compression and decompression in which a template adaptable to arithmetic encoding and decoding processes is produced from an image to be processed with respect to each pixel so that the image is encoded into a compressed image and the compressed image is decoded into a reconstructed image by using the template.
In order to compress image data obtained through raster scanning of an original document, several coding methods are commonly used: the Modified Huffmann (MH) coding method and the Modified READ (MR) coding method, the standard coding methods intended for use with G3 facsimile apparatus; and the Modified MR (MMR) coding method, the standard coding method intended for use with G4 facsimile apparatus. A predictive coding method is also one of such coding methods, but it is a non-standard coding method. In this conventional method, a template is used to predict the color for a target pixel of an image in the image coding process FIG. 1 shows an example of the template used by the conventional predictive coding system. In FIG. 1, a target pixel of an image to be processed is labeled as "x", while eight pixels preceding the target pixel "x" as the reference pixels are labeled as "a" through "h". The colors for the reference pixels "a" through "h" are detected with respect to each target pixel in the image. In a case where a template including eight reference pixels is used, 256 different states of colors of the reference pixels (Markov conditions) are definable with respect to one target pixel. A particular state of the colors of the reference pixels is identified by a state index, the state index in the above case ranging from 0 to 255. The template used in the predictive coding method is a set of data including relative locations of the reference pixels surrounding the target pixel.
Because the probability of occurrence of color for the target pixel is closely related with the state of colors for the reference pixels in the template, a predicted probability of color for the target pixel can be determined according to the state of colors of the template. For example, if all the colors for the reference pixels surrounding the target pixel are white, white is the color which most probably occurs for the target pixel. The probabilities of color occurrences for picture elements are generally predetermined via a statistical method by observing the colors of the reference pixels in the template.
In the predictive coding method described above, a coincidence between the predicted color of the target pixel being predicted through the template and the actual color of the target pixel is detected with respect to each of the pixels of an image. Then, a stream of data including state index data and coincidence data is produced: the state index data indicating a state of colors of pixels in each template, and the coincidence data indicating a condition of coincidences between the predicted colors and the actual colors. A run-length coding process is performed by repeatedly detecting one state index and one coincidence data from the stream of data so that the original image can be compressed.
The predictive coding process can be efficiently performed if the state index data for all the target pixels is stored in a memory and the run-length coding process is performed by detecting the state index data stored in the memory. However, it is necessary to store the stream of data indicating coincidence between the predicted color and the actual color sequentially in the order of the pixels being detected in order to efficiently perform the predictive coding process. Thus, there is a problem in that the size of the coding system becomes large because the memory for storing a large amount of data is required, and thus it is difficult to accomplish real-time processing of the image compression or decompression.
In order to eliminate the above described problem and to improve the efficiency of the coding process, a combined coding method in which the predictive coding method and an arithmetic coding method are combined has been proposed.
Conceptually, the basis for the arithmetic coding method is a recursive probability interval division. An input sequence of symbols is mapped into a real number "x" on the interval [0.0, 1.0) where a square bracket on the left-hand end of the interval denotes equality being allowed and a curved bracket on the right-hand end thereof denotes equality being disallowed. In the arithmetic coding method, the binary expansion of the real number "x" is transmitted or stored instead of the original sequence of symbols. A QM-coder which utilizes the concept of the arithmetic coding method has been proposed.
FIG. 2 shows an example of such an interval division through an initial sequence of symbols 0, 1, 0, 0 to be coded. The portion of [0.0, 1.0) on which x is known to lie after coding an initial sequence of symbols is known as the current coding interval. For each binary input the current coding interval is divided into two sub-divisions with sizes proportional to the relative probabilities of symbol value occurrences. The new current coding interval becomes that associated with the symbol value which has actually occurred. In an encoder, knowledge of the current coding interval is maintained in a variable giving its size and a second variable giving its base. The output stream is obtained from the variable pointing to the base.
In FIG. 2, when a first symbol is encoded, the current coding interval [0.0, 1.0) is divided into two sub-intervals A(0) and A(1) according to the probabilities of symbol occurrences. If the symbol "0" actually occurs in a sequence of symbols, the sub-interval A(0) is selected and this sub-interval becomes the current coding interval. Then, when a second symbol is encoded, the current coding interval A(0) is divided into two sub-intervals A(00) and A(01) according to the probabilities of symbol occurrences. If the symbol "1" actually occurs, the sub-interval A(01) is selected and this sub-interval becomes the current coding interval. The above procedures are repeated until the end of the sequence of symbols is encoded.
When the current coding interval is partitioned into two sub-intervals, the sub-interval for the less probable symbol (LPS) is placed in an order higher than that of the sub-interval for the more probable symbol (MPS). Therefore, when the LPS is coded, the MPS sub-interval is added to the base. This coding procedure requires that symbols be recognized as either MPS or LPS, rather than 0 or 1. Consequently, the size of the LPS interval and the sense of the MPS for each symbol must be known in order to code that symbol. Because the code stream always points to a real number in the current coding interval, the decoding process is a matter of determining, for each decision, which sub-interval is being pointed to by the code stream. This procedure is also done recursively, using the same interval sub-division process as in the case of the encoder. Each time a decision is decoded, the decoder subtracts any interval which is added to the code stream by the encoder. Therefore, the code stream in the decoder indicates the current coding interval relative to the base of the current coding interval. Because the coding process involves addition of binary fractions rather than concatenation of integer code words, the more probable binary decisions can often be coded at a cost of much less than one bit per decision.
In the predictive coding process, the probability of symbol occurrence in the stream of symbols is varied according to the state index (or the context). The arithmetic coding method is suitable for such a coding process, as the use of such a method makes it possible to reduce the size of hardware or the capacity of the required memories and increase the efficiency of the coding process. Also, the arithmetic coding method is advantageous in that adaptive implementation as regards the existing image processing system is easy. A QM-coder is devised so as to efficiently perform the above mentioned arithmetic coding process using small sized hardware.
As described above, in the arithmetic coding process, if the-.MPS frequently occurs in the stream of symbols, the coding intervals for the symbols become wide and the amount of the data to be processed is reduced so that the efficiency of the coding process is increased. Conversely, if the LPS frequently occurs in the stream of symbols, the coding intervals become narrow and the amount of the data to be processed is increased so that the efficiency of the coding process is lowered. In order to improve the efficiency of the arithmetic coding process, a preprocessing for increasing the frequency of the MPS occurrence is needed. The predictive coding process described above is performed for such a purpose, and it enables the predicted probability of the color for the target pixel to have a greater value.
A method for making the value of the predicted probability of the color for the target pixel greater is to produce and use a template for recognizing the characteristics of image data to be coded. For example, the template shown in FIG. 1 is suitable for use in the preprocessing of a bi-level image (a black-white image) such as a character. FIG. 3A shows a template which is suitable for use in the preprocessing of a halftone image such as a photograph. FIG. 3B shows a template which is suitable for use in the preprocessing of a composite image in which a bi-level image and a halftone image coexist.
However, in the prior art, there is no appropriate method for preparing a template for recognizing the characteristics of local portions of an image to be encoded or decoded. Hence, it is difficult to enable the efficiency of the coding process to be increased without seriously degrading the picture quality. For example, an image which is reproduced from a black-white image such as a character may have a faded portion like a halftone image when the reproduced image is printed on a copy sheet in a poor printing condition. The location at which the faded portion appears and the halftone level thereof depend on the characteristics of the original image being processed. However, there conventionally is no appropriate method for preparing a template for recognizing the characteristics of the local portions of the image data so as to increase the efficiency of the encoding or decoding process.